package Sort.quickSort;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

import static Sort.SevenSort.inSertionSort;
import static Sort.SevenSort.swap;

/**
 * @author lumin
 * @date 2022/05/01 14:55
 **/
public class quickSorttest {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 在[l ... r]上进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
//        if(r - l <= 15){
//            inSertionSort(arr);
//            return;
//        }
        //获取分区点
        int p = partition(arr,l,r);
        //在左右区间上重复进行快速排序
        quickSortInternal(arr,l,p - 1);
        quickSortInternal(arr,p + 1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        //基准值
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if(arr[i] < v){
                swap(arr,j + 1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }

    public static void main(String[] args) {
        int[] arr = {2,1,5,3,2,4,8,5,9,8,7};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}